package leetcode_bin_tree_test;


import bin_tree.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 *  二叉搜索树的最近公共祖先
 */
public class LowestCommonAncestorSearch {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 递归
//        if (root.val < p.val && root.val < q.val) {
//            return lowestCommonAncestor(root.right, p, q);
//        }
//        if (root.val > p.val && root.val > q.val) {
//            return lowestCommonAncestor(root.left, p, q);
//        }
//        return root;

        // 两次遍历
//        List<TreeNode> pathP = getPath(root, p);
//        List<TreeNode> pathQ = getPath(root, q);
//        TreeNode ret = null; // 若不需要创建对象用来指代后面会出现的元素，直接赋值为空即可
//        for (int i = 0; i < Math.min(pathP.size(), pathQ.size()); i++) {
//            if (pathP.get(i).equals(pathQ.get(i))) {
//                ret = pathP.get(i);
//            } else {
//                break;
//            }
//        }
//        return ret;

        // 一次遍历
        TreeNode ret = null;
        while (true) {
            if (root.val > p.val && root.val > q.val) {
                root = root.left;
            } else if (root.val < p.val && root.val < q.val){
                root = root.right;
            } else {
                ret = root;
                break;
            }
        }
        return ret;
    }

    /**
     * 获取找到node的路径
     * @param root
     * @param node
     * @return
     */
    private List<TreeNode> getPath(TreeNode root, TreeNode node) {
        List<TreeNode> ret = new ArrayList<>();
        while (true) {
            ret.add(root);
            if (root.val == node.val) {
                break;
            }
            if (root.val > node.val) {
                // 在左子树
                root = root.left;
            } else {
                root = root.right;
            }
        }
        return ret;
    }
}
